<head>
    <meta charset="UTF-8">
<title>算法训练 Buying Sets</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <div>
<div>
<div>问题描述</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>给定n个集合, 要求选出其中某些集合, 使得这些集合的并集的势, 等于选出的集合的数目.</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>对于任意的k(1&lt;=k&lt;=n), 满从中选出任意k个集合, 这k个集合的并集的势一定大于等于k.</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>每个集合有一个权值, 每个选择方案的代价是所选的集合的权值的和.</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>请输出代价最小的选择方案的代价.</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>当然, 不选择任何一个集合是一个可行的方案(权值和为0), 但不一定最优(权值和可以为负).</div>
<div>&nbsp;</div>
<div>输入格式</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>第一行一个正整数n(1&lt;=n&lt;=300), 为集合个数.</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>在接下来n行中, 第i行描述第i个集合:</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>首先给出一个正整数m[i]为该集合的势, 显然1&lt;=m[i]&lt;=n.</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>接下来m[i]个在1到n之间的整数, 表示该集合中的元素.</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>最后一行n个整数, 为每个集合的权值, 绝对值不超过1e6.</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span></div>
<div>输出格式</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>仅一个整数, 为代价最小的选择方案的代价.</div>
<div>&nbsp;</div>
<div>样例输入1</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>3</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>1 1</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>2 2 3</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>1 3</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>10 20 -3</div>
<div>样例输出1</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>-3</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span></div>
<div>样例输入2</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>5</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>2 1 2</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>2 2 3</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>2 3 4</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>2 4 5</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>2 5 1</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>1 -1 1 -1 1</div>
<div>样例输出2</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>0</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span></div>
<div>样例输入3</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>5</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>2 1 2</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>2 2 3</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>2 3 4</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>2 4 5</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>2 5 1</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>-1 1 -1 1 -1</div>
<div>样例输出3</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>-1</div>
</div>
</div>